package codeRandomThoughts.Test763划分字母区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        int len = s.length();
        int[][] alphabetRange = new int[26][2];

        //把里面的值初始化为-1
        for (int[] ints : alphabetRange) {
            Arrays.fill(ints,-1);
        }

        for (int i = 0; i < len; i++) {
            //初始化每个字母的出现位置和结束位置
            char c = s.charAt(i);
            int index = c - 'a';
            //出现位置
            if (alphabetRange[index][0] == -1) {
                //说明第一次遍历到
                alphabetRange[index][0] = i;
            }

            //结束位置
            alphabetRange[index][1] = i;
        }

        //把alphabet按照出现位置升序排序
        Arrays.sort(alphabetRange, (a1, a2) -> {
            return Integer.compare(a1[0], a2[0]);
        });

        List<Integer> result = new ArrayList<>();
        int end = 0;
        int begin = 0;
        //遍历每个字母的出现范围,如果有交叉,取并集
        for (int[] range : alphabetRange) {
            //如果字母没出现过,直接跳过
            if (range[0] == -1) continue;

            //如果字母范围有交叉
            if (range[0] < end) {
                //扩大范围,取并集
                end = Math.max(range[1], end);
            } else {
                //没有交叉,此时要分出一个新的片段
                //根据题意,我们记录前一段的长度
                result.add(end - begin + 1);
                begin = range[0];
                end = range[1];
            }
        }
        //添加最后一个片段
        result.add(end - begin + 1);

        //去除一开始添加的无用片段
        result.remove(0);
        return result;
    }
}
